package com.stefan.queue;
/*
* 思路 - 链表的头插法和尾取法，尾插法，头取法 可实现queue FIFO
*
* */
public class LinkedListStefanQueue<E> implements StefanQueue<E>{
    private int capacity; //限制循环链表的长度
    private int size; //记录当前列表的size
    private Node<E> head,tail;

    public LinkedListStefanQueue() {
        this.capacity = 5; // default 5
    }

    public LinkedListStefanQueue(int capacity) {
        this.capacity = capacity;
    }

    static class Node<E> {
        E element;
        Node<E> next;

        public Node (E element) {
            this.element = element;
            next = null;
        }

    }

    @Override
    public void enqueue(E element) {
        if (isFull()) {
            return; // 丢弃
        }
        Node<E> node =  new Node<>(element);
        if (head == null) {
            head = node;
            tail = node;
            node.next = head; //循环链表
        } else {
            node.next = head; //头插法
            tail.next = node; //循环链表
            head = node;//设置新head
        }
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            return null;
        }
        Node var = head;
        do {
            if (var.next == tail) {
                break;
            }
            var = var.next;
        } while (var != head);

        //拿到了倒数第二个Node
        E result = tail.element; //返回现在的tail的数据

        var.next = head; //剔除tail
        tail = var; //设置倒数第二node为tail
        size--;
        if (isEmpty()) {
            head = null;
            tail = null;
        }
        return result;
    }

    @Override
    public boolean isFull() {
        return this.size == this.capacity;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public int size() {
        return this.size;
    }

    public static void main(String[] args) {
        StefanQueue<Integer> stefanQueue = new LinkedListStefanQueue<>(5);
        stefanQueue.enqueue(1);
        stefanQueue.enqueue(2);
        stefanQueue.enqueue(3);
        stefanQueue.enqueue(4);
        stefanQueue.enqueue(5);
        stefanQueue.enqueue(6); //队列满了，放不进
        System.out.println("======");
        System.out.println(stefanQueue.dequeue());//消费 1
        stefanQueue.enqueue(6);//在放，1的位置应该是6
        stefanQueue.enqueue(7);//在放，队列满了，放不进
        System.out.println(stefanQueue.dequeue());//消费2
        stefanQueue.enqueue(7);//2的位置为7
        System.out.println(stefanQueue.dequeue());//消费3
        System.out.println(stefanQueue.dequeue());//消费4
        System.out.println(stefanQueue.dequeue());//消费5
        System.out.println(stefanQueue.dequeue());//消费6
        System.out.println(stefanQueue.dequeue());//消费7
        System.out.println(stefanQueue.dequeue());//队列为空，消费不了
        stefanQueue.enqueue(8);//3的位置为8
        stefanQueue.enqueue(9);//4的位置为9
        stefanQueue.enqueue(10);//5的位置为10
        System.out.println("=====");
        }
}
